/*
https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/solution/di-k-ge-zui-xiao-de-su-shu-fen-shu-by-le-argw/
 */
import java.util.Arrays;

public class Solution786 {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        double l=0.0,r=1.0;
        int x=0,y=0;
        while (true){
            double m=(l+r)/2;
            double max=0.0;
            int count=0;
            int i=0;
            for (int j=1;j<arr.length;j++){
                while ((double)arr[i]/arr[j]<m){
                    if ((double)arr[i]/arr[j]>max){
                        max=(double)arr[i]/arr[j];
                        x=arr[i];
                        y=arr[j];
                    }
                    i++;
                }
                count+=i;
            }
            if (count==k){
                return new int[]{x,y};
            }else if (count>k){
                r=m;
            }else{
                l=m;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution786().kthSmallestPrimeFraction(new int[]{1,2,3,5},3)));
    }
}
